from Node import Node

class Graph:
    nodeList = []

    def GeneratetNodes(self, labyrinth, x, y):

        for i in range(y):
            for j in range(x):
                if labyrinth[j][i] == 1:
                    self.nodeList.append(Node(i,j,1))
                elif labyrinth[j][i] == 2:
                    self.nodeList.append(Node(i,j,2))
                elif labyrinth[j][i] == 3:
                    self.nodeList.append(Node(i,j,3))

    def GenerateLinks(self):
        for i in self.nodeList:
            for j in self.nodeList:
                if i.iXcoord - 1 == j.iXcoord and i.iYcoord == j.iYcoord:
                    i.next.append(j)
                elif i.iXcoord + 1 == j.iXcoord and i.iYcoord == j.iYcoord:
                    i.next.append(j)
                elif i.iXcoord == j.iXcoord and i.iYcoord - 1 == j.iYcoord:
                    i.next.append(j)
                elif i.iXcoord == j.iXcoord and i.iYcoord + 1 == j.iYcoord:
                    i.next.append(j)

    def printNodes(self):
        for i in self.nodeList:
            print(i.iXcoord,',',i.iYcoord)
            for n in i.next:
                print(n.iXcoord,',',n.iYcoord,':',end = " ")
                print()
            print()

    def NodeIsNotInList(self, list, node):
        for n in list:
            if(n.iXcoord == node.iXcoord and n.iYcoord == node.iYcoord):
                return False
        return True

    def TreeSearchDepth(self, node):
        frontier = [node]
        path = []
        count = 0
        while len(frontier) > 0:
            s = frontier.pop(0)
            print(s.iXcoord,':',s.iYcoord)
            count += 1
            if s.itype == 3:
                print( 'Depth takes ',count,'turns' ) 
                return s
            path = path + [s]
            for n in s.next:
                if(self.NodeIsNotInList(path, n)):
                   frontier = [n] + frontier
        print( 'Depth takes ',count,'turns' )
        return 0

    

    def findNode(self, x, y):
        for n in self.nodeList:
            if(n.iXcoord == x and n.iYcoord == y):
                return n
        return 0

    def findDestDepth(self, x, y):
        node = self.findNode(x, y)
        destNode = self.TreeSearchDepth(node)
        if destNode != 0:
            return destNode.iXcoord, destNode.iYcoord
        else:
            return -1,-1

    def TreeSearchBreadth(self, node):
        frontier = [node]
        path = []
        count = 0
        while len(frontier) > 0:
            s = frontier.pop(0)
            print(s.iXcoord,':',s.iYcoord)
            count += 1
            if s.itype == 3:
                print( 'Breadth takes ',count,'turns' ) 
                return s
            path = path + [s]
            for n in s.next:
                if(self.NodeIsNotInList(path, n)):
                   frontier = frontier + [n]
        print( 'Breadth takes ',count,'turns' )
        return 0

    def findDestBreadth(self, x, y):
        node = self.findNode(x, y)
        destNode = self.TreeSearchBreadth(node)
        if destNode != 0:
            return destNode.iXcoord, destNode.iYcoord
        else:
            return -1,-1

    def ManhattanDistance(self,node):
        x = abs(node.iXcoord - 6)
        y = abs(node.iYcoord)
        return x + y

    def ReconstructPath(self,pathBack, lastNode):
        path = [lastNode]
        
        while(not(lastNode.itype == 2)):
            for prevNode, thisNode in pathBack.items():
                if prevNode == lastNode:
                    lastNode = thisNode
                    #print(lastNode.iXcoord, ',' , lastNode.iYcoord)
                    path = [lastNode] + path
                    break
                    
        #for n in path:
            #print(n.iXcoord, ',' , n.iYcoord)
        return path

        


    def TreeSearchAStar(self, node):
        costs = ()
        frontier = [node]
        costDict = {}
        pathDict = {}
        path = []
        count = 0
        while len(frontier) > 0:
            node = frontier[0]
            if node in costDict:
                costs = costDict[node]
                mincost = costs[0] + costs[1]
            for n in frontier:
                if n in costDict:
                    costs = costDict[n]
                    cost = costs[0] + costs[1]
                    if(cost < mincost):
                        mincost = cost
                        node = n
            
            if node.itype == 3:
                print( 'A* takes ',count,'turns' )
                path = self.ReconstructPath(pathDict, node) 
                return node, path
            
            frontier.remove(node)
            path = path + [node]
            print(node.iXcoord,':',node.iYcoord)
            count += 1
            
            for n in node.next:
                #Calculate score
                if node in costDict:
                    costs = costDict[node]
                    score = self.ManhattanDistance(n) + costs[0] + 1
                else:
                    score = self.ManhattanDistance(n)

                if(n in path):
                    #pathDict[node] = n
                    if n in costDict:
                        costs = costDict[n]
                        oldcost = costs[0] + costs[1]
                        if(score < oldcost):
                            path.remove(n)
                            frontier = frontier + [n]
                elif(n in frontier):
                    #pathDict[node] = n
                    cost1 = costDict[n]
                    oldcost1 = cost1[0] + cost1[1]
                    tempcost = costDict[node]
                    costs = (tempcost[0] + 1, self.ManhattanDistance(n))
                    if costs < oldcost1:
                        costDict[n] = costs
                        pathDict[n] = node
                else:
                    pathDict[n] = node
                    if node in costDict:
                        tempcost = costDict[node]
                        costs = (tempcost[0] + 1, self.ManhattanDistance(n))
                        costDict[n] = costs
                    else:
                        costs = (1,self.ManhattanDistance(n))
                        costDict[n] = costs
                    frontier = frontier + [n]

                
        print( 'Breadth takes ',count,'turns' )
        return 0

    def findDestAStar(self, x, y):
        path = []
        node = self.findNode(x, y)
        destNode,path = self.TreeSearchAStar(node)
        if destNode != 0:
            return destNode.iXcoord, destNode.iYcoord, path
        else:
            return -1,-1, path

    

    